/*
 * @lc app=leetcode.cn id=2039 lang=cpp
 *
 * [2039] 网络空闲的时刻
 */

// @lc code=start
class Solution
{
    typedef pair<int, int> PII;

public:
    int networkBecomesIdle(vector<vector<int>> &edges, vector<int> &patience)
    {
        int n = patience.size();
        vector<vector<int>> adj(n);
        vector<int> visited(n, 0);
        for (auto &v : edges)
        {
            adj[v[0]].push_back(v[1]);
            adj[v[1]].push_back(v[0]);
        }

        queue<PII> que;
        que.emplace(PII(0, 0));
        visited[0] = 1;
        int ans = 0;
        while (!que.empty())
        {
            auto [idx, step] = que.front();
            que.pop();
            for (auto next : adj[idx])
            {
                if (visited[next])
                {
                    continue;
                }
                que.emplace(PII(next, step + 1));
                visited[next] = 1;
                int time = patience[next] * ((2 * (step + 1) - 1) / patience[next]) + (2 * (step + 1) + 1);
                ans = max(ans, time);
            }
        }

        return ans;
    }
};
// @lc code=end
